package acwing.dfs;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 树的重心。
 * 策略：
 * 1. dfs均可将一个连通图中的点遍历完，dfs使用更简洁，一般无特殊要求可用dfs
 * 2. 每次dfs时，返回dfs的结点的子树大小sum，故对于每个儿子返回的sum值，当前结点做以下处理：
 * 3. 比较各个子树的sum选择一个最大值；此外，除了这个子树后剩余的部分的个数也参与比较
 * 4. 注意：这是一颗树，故任何一个结点都可以作为主根向下遍历
 */
public class 树的重心 {

    static int N = 100010;
    static int M = 2 * N;
    static int ans = N; // 没个节点重心最大的节点数
    static int idx;
    static int n;
    static int[] h = new int[N]; //邻接表存储树，有n个结点，需要n个队列头结点
    static int[] e = new int[M]; // 存元素
    static int[] ne = new int[M]; // 存next的值
    static boolean[] st = new boolean[N]; // 标记每个节点是否被访问过

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        Arrays.fill(h,-1); //全初始化为-1
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a, b);
            add(b, a);
        }
        dfs(1);
        System.out.println(ans);
    }

    private static int dfs(int u) {
        st[u] = true;
        int sum = 1; //当前子树大小，包括自己故从1开始
        int res = 0; //删除该结点后每一个连通块大小的最大值
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!st[j]) {
                int s = dfs(j); //其儿子子树的大小
                res = Math.max(res, s);
                sum += s; // //以u为根节点的子树大小
            }
        }
        res = Math.max(res, n - sum);
        ans = Math.min(res, ans);
        return sum;
    }

    /**
     * 插入一条a指向b的边
     * 就是在a这个单链表里插入b
     * @param a
     * @param b
     */
    private static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;

    }

}
